/*
Write a C++ function to print all the elements less than the key element in binary search tree
*/


#include<iostream.h>
#include<conio.h>

class Node 
{
      public:
             int data;
             Node *lchild, *rchild;
             Node(int value)
             {
                 data = value;
                 lchild = rchild = NULL;
             }
      
};

class BSTree
{
      public:
             void insert(int value);
             void inorderDisplay();
             void printSmaller(int value);
             Node *root;
             BSTree()
             {
                     root = NULL;
             }
      private:
              void insert(Node **root, int value);
              void inorderDisplay(Node *root);
              void printSmaller(Node* root,int value);
};
void BSTree :: inorderDisplay(Node *root)
{
     if(root ==  NULL)
          return ;
     inorderDisplay(root->lchild);
     cout<<"   "<< root->data;
     inorderDisplay(root->rchild);          
}
void BSTree :: inorderDisplay()
{
     inorderDisplay(root);
}
void BSTree :: insert(Node **root, int value)
{
     Node *newNode = new Node(value);
     if(*root == NULL)
     {
          *root = newNode;
     }
     else
     {
         Node *currNode = *root;
               if(currNode->data > value)
                       insert(&currNode->lchild, value);
               if(currNode->data < value)
                     insert(&currNode->rchild,value);
     }
}
void BSTree :: insert(int value)
{
     insert(&root, value);
}

void BSTree :: printSmaller(Node *root, int value)
{
     if(root == NULL)
         return ;
     printSmaller(root->lchild, value);
     if(root->data <= value)
         cout<<" "<<root->data;
     else
         return ;
     printSmaller(root->rchild, value);
}
void BSTree :: printSmaller(int value)
{
     printSmaller(root, value);
}
int main()
{
    BSTree bstree;
    bstree.insert(5);
    bstree.insert(7);
    bstree.insert(3);
    bstree.insert(6);
    bstree.insert(8);
    bstree.insert(1);
    bstree.insert(4);
    bstree.inorderDisplay();
    cout<<"\n Displays the smaller elements then the given key value\n";
    bstree.printSmaller(6);
    getch();
    return 0;
}
